package demo6;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
//    //1.面试题13. 机器人的运动范围(回溯)
//    private boolean[][] path;
//    private int count;
//    public int movingCount(int m, int n, int k) {
//        this.path = new boolean[m][n];
//        dfs(0, 0, m, n, k);
//        return count;
//    }
//    private void dfs(int x, int y, int m, int n, int k) {
//        if(x < 0 || x >= m || y < 0 || y >= n ||
//                sumCount(x, y) > k || path[x][y]) {
//            return;
//        }
//        path[x][y] = true;
//        count++;
//        dfs(x + 1, y, m, n, k);
//        dfs(x, y + 1, m, n, k);
//    }
//    private int sumCount(int x, int y) {
//        int sum = 0;
//        while(x > 0) {
//            sum += x % 10;
//            x /= 10;
//        }
//        while(y > 0) {
//            sum += y % 10;
//            y /= 10;
//        }
//        return sum;
//    }

    //2.剑指 Offer 46. 把数字翻译成字符串(动态规划)
    public int translateNum(int num) {
        //状态F(i):前i个数字的翻译方法
        //1:
        //a
        //12:
        //bc、m
        //122:
        //bcc、mc、bw
        //1225:
        //bccf、mcf、bwf、bcz、mz
        //转移方程：加上第i位的后两位小于25并且大于1:f[n] = f[n - 1] + f[n - 2];
        //初始化:f[0] = 1, f[1] = 1;
        String str = String.valueOf(num);
        int len = str.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= len; i++) {
            String s = str.substring(i - 2, i);
            if(s.compareTo("10") >= 0 && s.compareTo("25") <= 0) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[len];
    }

    //3.丑数(动态规划)
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int a = 1;
        int b = 1;
        int c = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
            if(dp[a] * 2 == dp[i]) {
                a++;
            }
            if(dp[b] * 3 == dp[i]) {
                b++;
            }
            if(dp[c] * 5 == dp[i]) {
                c++;
            }
        }
        return dp[n];
    }
    //4.目标和(动态规划)
    private int count;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return count;
    }
    private void dfs(int[] nums, int target, int index, int sum) {
        if(sum == target && index == nums.length) {
            count++;
        }
        if(index >= nums.length) {
            return;
        }
        dfs(nums, target, index + 1, sum + nums[index]);
        dfs(nums, target, index + 1, sum - nums[index]);
    }
    //5.零钱兑换(动态规划)
    public int coinChange(int[] coins, int amount) {
        //状态dp[j]: 表示钱包价值为j时，所需要的最小硬币个数
        //转移方程dp[j] = dp[j - coins[i]] + 1
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                if(dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    //6.分割等和子集(动态规划)
    public boolean canPartition(int[] nums) {
        //状态dp[i][j]:表示从前i个商品中取元素，放入大小为j的背包中，是否能装满
        //转移方程if(j - num >= 0) dp[i][j] = dp[i - 1][j - num] || dp[i - 1][j] 可以装也可以不装
        // if(j - num < 0) dp[i][j] = dp[i - 1][j];//装不下就别装

        //先求出所有和
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % 2 == 1) {//特判，如果和是奇数，那么肯定不能等和分割
            return false;
        }
        //只要能装满一半即可
        int col = sum / 2;
        int row = nums.length;
        boolean[][] dp = new boolean[row][col + 1];
        //初始化第一行，只能让装下第一个元素的背包大小为true
        if(col > nums[0]) {
            dp[0][nums[0]] = true;
        }
        //第一列肯定可以装满
        for(int i = 0; i < row; i++) {
            dp[i][0] = true;
        }
        //开始递推
        for(int i = 1; i < row; i++) {
            for(int j = 1; j <= col; j++) {
                //至少是上一行的状态(可以装也可以不装，这里至少可以是不装)
                dp[i][j] = dp[i - 1][j];
                //在进行修改
                if(j > nums[i]) {//这里背包空间很大，可以装也可以不装
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                } else if(j == nums[i]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[row - 1][col];
    }

    //7.最佳买卖股票时机含冷冻期(动态规划)
    public int maxProfit(int[] prices) {
        //有三种状态：不持股当天没卖出、持股但是卖出了、持股
        //状态转移方程:
        //不持股当天没卖出(1.昨天持股但是卖出了；2.昨天不持股):dp(i, 0) = Math.max(dp[i - 1][1], dp[i - 1][0]);
        //持股但是卖出了(1.昨天持股没卖出) dp[i, 0] = dp[i - 1][2] + prices[i];
        //持股(1.昨天持股; 2.昨天不持股没卖出) dp[i, 0] = Math.max(dp[i - 1][2], dp[i - 1][0] - prices[i]);
        int len = prices.length;
        int[][] dp = new int[len][3];
        //初始化
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = -1 * prices[0];
        for(int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0]);
            dp[i][1] = dp[i - 1][2] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] - prices[i]);
        }
        //最后一定是不持股的两种情况，比较最大值即可
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }
//
//    //8字符串分割(回溯)
//    private List<List<String>> ret = new ArrayList<>();
//    private List<String> path = new ArrayList<>();
//    public List<List<String>> partition(String s) {
//        List<Integer> path = new ArrayList<>();
//        dfs(s, 0);
//        return ret;
//    }
//    private void dfs(String s, int began) {
//        if(began >= s.length()) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = began; i < s.length(); i++) {
//            if(isValue(s, began, i)) {
//                String str = s.substring(began, i + 1);
//                path.add(str);
//            } else {
//                continue;
//            }
//            dfs(s, i + 1);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private boolean isValue(String s, int left, int right) {
//        while(left < right) {
//            if(s.charAt(left) != s.charAt(right)) {
//                return false;
//            }
//            left++;
//            right--;
//        }
//        return true;
//    }

    //9.子集(II 回溯)
    private List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<Integer> path = new ArrayList<>();
        boolean[] flag = new boolean[nums.length];
        dfs(nums, path, flag);
        return ret;
    }

    private void dfs(int[] nums, List<Integer> path, boolean[] flag) {
        if(!ret.contains(path)) {
            ret.add(new ArrayList<>(path));
        }
        for(int i = 0; i < nums.length; i++) {
            if(flag[i]) {
                continue;
            }
            if(!path.isEmpty() && path.get(path.size() - 1) > nums[i]) {
                continue;
            }
            path.add(nums[i]);
            flag[i] = true;
            dfs(nums, path, flag);
            path.remove(path.size() - 1);
            flag[i] = false;
        }
    }

    //10.整数拆分(动态规划)
    public int integerBreak(int n) {
        //dp[i]:拆分数字i，可以得到的最乘积
        //转移方程:dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                //这里为什么要判断dp[i - j] * j 和 (i - j) * j ?
                //是因为dp[i - j]不包括i - j这个整数，而是对他的拆解
                dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
            }
        }
        return dp[n];
    }
}


//class Main {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        solution.partition("aab");
//
//    }
//}

